/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package insert;

import org.junit.Test;

import java.util.Arrays;

/**
 * <p>
 * 希尔排序
 * </p>
 * @author LvJing
 * @version $Id:ShellSort.java v1.0 2018/7/21 上午10:02 LvJing Exp $
 */
public class ShellSort {

    /*
    希尔排序
    基本思想：先把整个数组分成多个序列进行直接插入排序，这样序列不断变小，数组变得接近有序，最后对全体记录做一次直接插入排序。
    操作方法：先对数组进行分组，在这个分组里按照直接插入排序，把大的放后面，小的放前面。分组的间隔一般为数组长度的一半。
     */

    public void shellSort(int[] arr) {
        if (arr == null || arr.length == 0 || arr.length == 1) {
            return;
        }

        int length = arr.length;

        // 每次分组排序后，下次间隔为上次的一半
        for (int increment = length/2; increment > 0; increment /= 2) {

            // 分组内依然是直接插入排序
            for (int i = increment; i < length; i++) {
                int temp = arr[i];
                int j;
                for (j = i; j >= increment && temp < arr[j - increment]; j -= increment) {
                    arr[j] = arr[j - increment];
                }
                arr[j] = temp;
            }
        }
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 2, 6, 4, 8, 11, 5};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
